//给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 
//
// 说明：解集不能包含重复的子集。 
//
// 示例: 
//
// 输入: nums = [1,2,3]
//输出:
//[
//  [3],
//  [1],
//  [2],
//  [1,2,3],
//  [1,3],
//  [2,3],
//  [1,2],
//  []
//] 
// Related Topics 位运算 数组 回溯算法


package leetcode.d_1_99;

import java.util.ArrayList;
import java.util.List;

//Java：子集
public class P78Subsets{
    public static void main(String[] args) {
        P78Subsets solution = new P78Subsets();
        System.out.println(solution.subsets(new int[]{1,2,3})); // [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null){
            return res;
        }
        dfs(res, nums, new ArrayList<Integer>(), 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, int[] nums, List<Integer> list, int index) {
        if (index == nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }

        dfs(res, nums, list, index + 1);

        list.add(nums[index]);
        dfs(res, nums, list, index + 1);

        list.remove(list.size() - 1);
    }

}